package lib

import (
	"math/rand"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         380,
		Discription: "O(1)时间插入、删除、获取随机元素",
		Level:       2,
		Labels: map[string]int{
			"哈希表": 1,
		},
	})
}

// O（1）删除：适合双向链表
// O（1) 取随机：适合数组
// 综合：用数组存方便随机，再用哈希表存储值到索引的映射，方便删除、判断元素是否存在；当删除时，把数组最后一个元素换到被删除的索引位置，再删除最后一个元素
type RandomizedSet struct {
	nums []int
	//记录每一个值的索引位置
	indexMap map[int]int
}

func Constructor9() RandomizedSet {
	return RandomizedSet{
		nums:     make([]int, 0),
		indexMap: make(map[int]int, 0),
	}
}

func (set *RandomizedSet) Insert(val int) bool {
	if _, exist := set.indexMap[val]; exist {
		return false
	}

	set.indexMap[val] = len(set.nums)
	set.nums = append(set.nums, val)
	return true
}

func (set *RandomizedSet) Remove(val int) bool {
	removedIndex, exist := set.indexMap[val]
	if !exist {
		return false
	}

	n := len(set.nums)
	set.nums[removedIndex] = set.nums[n-1]
	set.indexMap[set.nums[n-1]] = removedIndex
	set.nums = set.nums[:n-1]
	delete(set.indexMap, val)
	return true
}

func (set *RandomizedSet) GetRandom() int {
	return set.nums[rand.Intn(len(set.nums))]
}
